package com.gxc.array;

/**
 *
 45. 跳跃游戏 II
 给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。
 每个元素 nums[i] 表示从索引 i 向后跳转的最大长度。换句话说，如果你在 nums[i] 处，你可以跳转到任意 nums[i + j] 处:
 0 <= j <= nums[i]
 i + j < n
 返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]。
 */
public class Jump {

    public static void main(String[] args) {
        System.out.println(handle(new int[]{2,3,1,1,4}));
        System.out.println(handle(new int[]{2,3,0,1,4}));
        System.out.println(handle(new int[]{0}));
        System.out.println(handle(new int[]{1,2}));
        System.out.println(handle(new int[]{2,2}));
        System.out.println(handle(new int[]{1,1, 1, 1}));
    }

    public static int handle(int[] nums) {
        if (nums.length == 1) return 0;
        int index = 0, start = 0;
        int time = 0;
        int step = 0;
        while (index < nums.length) {
            time++;
            if (index + nums[index] >= nums.length - 1) return time;
            int l = 1;
            int max = 0;
            start = index;
            step = nums[index];
            while (l<step + 1) {
                if (index + l + nums[index + l] > max) {
                    start = index + l;
                    max = index + l + nums[index + l];
                    if (max >= nums.length-1) return time+1;
                }
                l++;
            }
            index = start;
        }
        return time;
    }

    public int jump(int[] nums) {
        int length = nums.length;
        int end = 0;
        int maxPosition = 0;
        int steps = 0;
        for (int i = 0; i < length; i++) {
            maxPosition = Math.max(maxPosition, i + nums[i]);
            if (i == end) {
                end = maxPosition;
                steps++;
            }
        }
        return steps;
    }
}
